ABC204 D - Cooking
問題
ナップザックDPみたいなDP問題でした。
既存の解説を読んでもなかなか理解出来なかったのでもう少しくどい解説を書いてみる。
貪欲法では解けない
最初、以下のように単純に短い方に積んでいくという解法を試したけど通らなかった。
code:kotlin
fun problem204d(n: Int, t: List<Int>): Long {
val t = t.sortedDescending()
var a = 0L
var b = 0L
for (i in 0 until n) {
if (a <= b) {
a += ti
} else {
b += ti
}
}
return Math.max(a, b)
}
ちなみに
5
2 2 2 3 3
とかでダメそう＞＜
解説を読む
本番中には解けなかったため解説ACを目指した。
公式解説を読んでみたけど、結構思考の工程が省略されている感じの解説だったのでなかなか理解できなかった。
https://gyazo.com/ca6f964c9543ad39537162a4fe9a607f
DPで解けるらしいけど、どうすればこの問題をDPに落とし込めるのか。
解説を読み解いてみたい。
まず以下の部分。
code:text
T1+…+TNをSとします。1つ目のオーブンを使う時間が2つ目のオーブンを使う時間以上であると仮定してよいです(そうでない場合、2つのオーブンを入れ替えれば良い)。このとき、1つ目のオーブンを使う時間は S/2以上になります。
オーブン１とオーブン２の２つにそれぞれの料理を分けるということは、内訳がどんな数であれ掛かる時間の合計を２つに分けるということになる。そのため、均等に分けられたとすると２つのオーブンが合計時間の半分ずつを取ることになる。均等じゃない場合は必ず片方の時間が増え、もう片方の時間が同じだけ減る。つまり多い方のオーブンは必ず合計時間の半分以上になることが分かるということ。
続いて以下の部分。
code:text
この条件下で1つ目のオーブンを使う時間を最小化すればよいので、問題は「T1,…,TNからいくつか選んだ和であって、S/2以上の最小値は？」と読み替えることができます。
１つ目のオーブンというのは値が多い方(調理時間が長い方)のオーブンということ。
求める値は「全ての料理を作るのに掛かる時間」なので、多い方のオーブンが最小になる組み合わせが正解になる。
ここからが重要。
code:text
この問題は「T1,…,TNからいくつか選んだ和をxにすることができるか？」という問題を各xに対して答えることができれば解けます。
xに出来るということは、つまりその組み合わせが実際に存在するということ。
そのため、選んだ和がとある数になる組み合わせが存在するかを順番に試していってメモしていき、その中で総和の半分以上かつ最小の数＝多い方のオーブンの掛かる時間＝求める値ということになる。
実装してみる
これをDPで実装する必要がある。
実装はそんなに複雑ではないので、順番に考えてみたい。
まず前処理としてsumとmaxを定義しておく。
code:kotlin
val sum = t.sum()
val max = (sum + 1) / 2
sumはそのままTの総和。maxはsumの半分の値だけど、割り切れない場合は大きい方の値を選びたいため、小数点以下を繰り上げる必要がある。
次にDPを定義する。
code:kotlin
val dp = Array(n + 1) { BooleanArray(sum + 1) { false } }
DPはn + 1 * sum + 1のboolean型二次元配列を使用する。
dp[i][x]のiはi番目の料理時点という意味。xは選んだ数の合計(料理に掛かる時間)で、dp[i][x]がtrueならi番目までの料理を使ってx時間にすることが出来るということ。
DPの実処理部分。
code:kotlin
// すべての料理
for (i in 1..n) {
// 0からすべての料理の総和まで
for (x in 0..sum) {
// もしひとつ前のiにその組み合わせが存在していたら
// 同じxはtrue。追加された料理を選ばないことも可能なため
// 同じxに新しい料理を追加した組み合わせもtrueになる
}
}
}
今回は制約も厳しくないので単純化するために一旦max以上という条件のことは忘れて、xの組み合わせが存在するかどうかのみを記録していく。
最後にmax(総和の半分以上)の中で一番時間が短い組み合わせを探して回答とする。
code:kotlin
for (i in max until sum + 1) {
}
コード全体は以下のようになった。
code:kotlin
fun main(args: Array<String>) {
val sc = Scanner(System.in)
val n = sc.nextInt()
val t = (0 until n).map { sc.next().toInt() }
println(problem204d(n, t))
}
fun problem204d(n: Int, t: List<Int>): Int {
val sum = t.sum()
val max = (sum + 1) / 2
val dp = Array(n + 1) { BooleanArray(sum + 1) { false } }
for (i in 1..n) {
for (x in 0..sum) {
}
}
}
for (i in max until sum + 1) {
}
return 0
}
感想
貪欲っぽい問題をDPに変換する考え方がむずかしかった。
ナップザックDPのように値自体を配列の添字にするというのも慣れないとなかなか上手く実装できない。